1) Field of the Invention
The present invention relates to a technology for performing multiple predictions simultaneously.
2) Description of the Related Art
In the technology disclosed in Japanese Application Laid-Open No. 2004-038323, a global history for performing branch prediction based on a branch history of branch instructions requires that branch information used for registering the branch history be transmitted one after another.
FIG. 8 illustrates the conventional branch prediction apparatus that uses the global history. An instruction fetch section 20 issues an instruction fetch request using an instruction fetch address generated by an instruction fetch address generation section 10, and indexes the branch history 200. The branch history 200 stores, in correlated form, the address of the branch instruction and the address of a branch destination predicted, thereby indexing the address of the branch destination from the address of the branch instruction.
In other words, when a branch instruction corresponding to the instruction fetch address is registered in the branch history 200, the instruction fetch section 20 reads the instruction address of the branch destination predicted by the branch history 200, to perform the next instruction fetch.
Moreover, the branch instruction fetched is decoded by an instruction decoder 30, registered in a branch reservation station 40, and executed. When the branch instruction is executed, either of branch information, “Taken” or “Not Taken”, is delivered to a global history 800.
The global history 800 stores the branch history of each branch instruction, and updates the branch history based on the branch information received. Then, the next branch direction of the branch instruction is predicted, based on the updated branch history, and a corresponding entry in the branch history 200 is updated based on the branch direction predicted.
Thus, in the branch prediction apparatus, the global history 800 predicts the branch direction using the branch history, and updates the branch history 200 based on the prediction. The branch history 200 predicts a branch destination based on the prediction result by the global history 800.
However, the conventional global history 800 requires that the branch information used for registering the branch history be transmitted one after another. Thus, only if all branch information is transmitted in a completely separate cycle, the branch information can be used and processed without damaging the information. However, if pieces of branch information are transmitted simultaneously, the global history 800 cannot process the information.
In super scalar processors and processors adopting the out-of-order execution method, instructions are executed depending on how conditions are satisfied and a plurality of instructions may be completed at the same time. Therefore, a plurality of branch instructions may be completed simultaneously. Thus, it is necessary that the global history be able to handle the branch instructions completed simultaneously.
Further, when the global history deals with pieces of branch information transmitted simultaneously, a plurality of updates of the branch history occurs simultaneously. Therefore, it is necessary that the branch history be able to process the simultaneous updates. However, usually the branch history is a random access memory (RAM), which has a limited number of input ports. Therefore, it is also necessary to limit the number of simultaneous updates, to match the number of input ports.